package likou;

/**
 * @author: 唐小尊
 * @email: 1171702529@qq.com
 * @cate: 2021/06/07 08:06
 */
public class _494 {
    public static void main(String[] args) {
        System.out.println(findTargetSumWays(new int[]{1,0},1));
    }
    public static int findTargetSumWays(int[] nums, int target) {
        return dfs(0, nums, target, 0);
    }

    public static int dfs(int start, int[] sums, int target, int now) {
        int jian = now - sums[start];
        int jia = now + sums[start];
        if (start == sums.length - 1) {
            if (jian == target && jia == target) {
                return 2;
            }else if (jian == target || jia == target){
                return 1;
            }else {
                return 0;
            }
        }
        return dfs(start + 1, sums, target, jian) + dfs(start + 1, sums, target, jia);
    }


    public int findTargetSumWays2(int[] nums, int target) {
        int sum = 0;
        for(int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        if(sum < target) {
            return 0;
        }
        if((sum + target) % 2 == 1) {
            return 0;
        }
        int bagSize = (sum + target) / 2;
        int[] dp = new int[bagSize + 1];
        dp[0] = 1;
        for(int i = 0; i < nums.length; i++) {
            for(int j = bagSize; j >= nums[i]; j--) {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[bagSize];
    }
}
